# -*- coding: utf-8 -*-

"""剑指 Offer II 080. 含有 k 个元素的组合
给定两个整数 n 和 k，返回 1 ... n 中所有可能的 k 个数的组合。

示例 1:
输入: n = 4, k = 2
输出:
[
  [2,4],
  [3,4],
  [2,3],
  [1,2],
  [1,3],
  [1,4],
]

示例 2:
输入: n = 1, k = 1
输出: [[1]]

提示:
1 <= n <= 20
1 <= k <= n"""

class Solution:
    """排列组合 - 回溯 - 递归
    终止条件（后）：i == hi || len(sub) == k
    有效结果（先）：len(sub) == k
    
    虽然提交成功，但是看题解，再加入剪枝操作后，操作效率明显提高。剪枝：剩下的元素再也凑不齐k个时"""
    def combine(self, n: int, k: int):
        nums, answer = list(range(1, n+1)), []
        hi = len(nums)
        def fork(i, sub):
            size = len(sub)
            # 剪枝操作
            if k-size > hi-i:
                return

            if size == k:
                answer.append(sub)
                return
            
            if i == hi:
                return
            
            new_sub = sub.copy()
            new_sub.append(nums[i])
            fork(i+1, new_sub)
            fork(i+1, sub)
        fork(0, [])
        return answer


if __name__ == '__main__':
    so = Solution()
    print(so.combine(n = 4, k = 2))
    print(so.combine(n = 1, k = 1))
